package leetcode.code1504;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：4 ms, 在所有 Java 提交中击败了91.70%的用户
 *
 * 内存消耗：39.8 MB, 在所有 Java 提交中击败了35.02%的用户
 *
 * 通过测试用例：73 / 73
 */
public class Solution implements IDebug {

	public int numSubmat(int[][] mat) {
//		H.printObject(mat);
		int ans = 0;
		int m = mat.length, n = mat[0].length;
		int[] sum = new int[n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int num = mat[i][j];
				sum[j] = num == 0 ? 0 : num + sum[j];
			}
			ans += this.f(sum, n);
		}
		return ans;
	}

	private int f(int[] sum, int n) {
		int[] stack = new int[n];
		int p = -1;
		int ans = 0;
		int i = 0;
		int zero = -1;
		while (i <= n) {
			int h = i < n ? sum[i] : 0;
			if (h == 0 || i == n) {
				if (p > -1) {
					int right = i - 1;// stack[p]
					while (p > -1) {
						int num = sum[stack[p--]];
//						while (p != -1 && sum[stack[p]] == num) {
//							p--;
//						}
						int left = p == -1 ? zero : stack[p];
						int len = right - left;
						h = p == -1 ? 0 : sum[stack[p]];
						ans += (num - h) * (len * (len + 1)) >> 1;
					}
				}
				zero = i;
				i++;
			} else {
				int right = i - 1;// stack[p--]
				if (p != -1 && sum[stack[p]] > h) {
					int num = sum[stack[p--]];
//					while (p > 0 && sum[stack[p - 1]] == num) {
//						p--;
//					}
					int left = p == -1 ? zero : stack[p];// + 1
					int len = right - left;// + 1
					if (p != -1) {
						h = Math.max(sum[stack[p]], h);
					}
					ans += (num - h) * (len * (len + 1)) >> 1;
				} else if (sum[i] != 0) {
					// 没有这句，里面有重复的高度，就得while推掉高度，右边界stack[p]，这句话省了两个while
					if (p == -1 || sum[stack[p]] != h) {// int right = i - 1;//stack[p]
						stack[++p] = i;
					}
					i++;
				} else {
					zero = i;
					i++;
				}
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(21, this.numSubmat(HelpDebug.str2array1("[[1,1,1,1,1,1]]")));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(5, this.numSubmat(HelpDebug.str2array1("[[1,0,1],[0,1,0],[1,0,1]]")));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(35, this.numSubmat(HelpDebug.str2array1("[[1,0,0,0],[1,1,0,0],[1,1,1,0],[1,1,1,1]]")));
	}

	@Override
	public void debug4() {
		HelpDebug.compare(30, this.numSubmat(HelpDebug.str2array1("[[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1]]")));
	}

	public void debug0() {
		HelpDebug.compare(15, this.numSubmat(HelpDebug.str2array1("[[0,1,0],[0,1,0],[0,1,0],[1,1,1]]")));
	}

	public void debug5() {
		HelpDebug.compare(24, this.numSubmat(HelpDebug.str2array1("[[0,1,1,0],[0,1,1,1],[1,1,1,0]]")));
	}

	public void debug6() {
		HelpDebug.compare(41, this.numSubmat(HelpDebug.str2array1("[[0,1,1,1],[1,1,0,1],[1,1,0,0],[1,1,1,1],[0,1,0,0]]")));
	}
	public void debug7() {
		HelpDebug.compare(96, this.numSubmat(HelpDebug.str2array1("[[1,1,1,1,0,1,0],[1,1,1,0,0,0,1],[0,1,1,1,1,0,0],[1,1,0,1,1,0,1],[1,0,0,0,0,0,1],[1,1,0,1,1,1,1],[1,1,0,0,1,1,1]]")));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug7();
		so.debug6();
		so.debug5();
		so.debug0();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
